Modern software development has embraced modular design and data abstraction. While this increases programmer productivity by enabling code reuse, it potentially creates additional performance problems. Examples include hidden algorithmic complexity where a linear-time algorithm encapsulated inside a simple application programming interface (API) call gives rise to quadratic complexity, when embedded inside an iterative loop. Software performance testing attempts to address these issues but faces two fundamental limitations—it is often too little or too late. First, due to resource constraints, a program is typically tested on only a small subset of its inputs and the performance problem may not manifest on these inputs. Second, these performance tests are time consuming and are typically only run periodically for large software projects. Consequently, many performance problems show up very late in the software development process when it is hard to redesign or re-architect the system to fix the problem correctly, or even worse, after software ships.
One difficulty encountered in computing complexity bounds is bounding the total number of loop iterations or recursive procedure call invocations. This is even more difficult for loops that iterate over abstract data-structures. In these cases, numerical functions over the data-structures may be used to express bounds, e.g., length of a list, height of a tree, etc. However, computing complexity bounds in these cases often requires sophisticated shape analysis, which involves understanding the shape/layout/reachability-pattern of a given data-structure, which in turn requires a sophisticated alias analysis that is known to be a hard problem.